#include <iostream>
#include <vector>
using namespace std;
int count = 0; 
bool IsSafe(const vector<int>& now) {
    if ((now[1] == now[2]) && (now[0]!= now[1]))
        return false;
    if ((now[2] == now[3]) && (now[0]!= now[2]))
        return false;
    return true;
}
// 备忘录函数，检查当前状态是否已经出现过
bool isRepeated(const vector<int>& now, const vector<int>& dira) {
    for (size_t i = 0; i < dira.size(); ++i) {
        int a = now[0] * 8 + now[1] * 4 + now[2] * 2 + now[3] * 1;
        if (dira[i] == a) {
            return true;
        }
    }
    return false;
}

// 输出过河步骤信息
void display(const vector<int>& dira) {
    for (size_t i = 0; i < dira.size(); ++i) {
        cout << dira[i] << " ";
    }
    cout << endl;
}

// 根据记录的步骤信息，输出具体的过河动作描述
void path(const vector<int>& dira) {
    for (size_t i = 0; i < dira.size() - 1; ++i) {
        int diff = dira[i] - dira[i + 1];
        switch (diff) {
        case 8:
        case -8:
            cout << "the farmer walked river alone\n";
            break;
        case 12:
        case -12:
            cout << "the farmer walk river with wolfs\n";
            break;
        case 10:
        case -10:
            cout << "the farmer walk river with chicken\n";
            break;
        case 9:
        case -9:
            cout << "the farmer walk river with millet\n";
            break;
        default:
            cout << "unknown action\n";
            break;
        }
    }
}

// 回溯法函数
void backtracking(vector<int>& now, vector<int>& dira, size_t step) {

    int a = now[0] * 8 + now[1] * 4 + now[2] * 2 + now[3] * 1;
    if (isRepeated(now, dira) ||!IsSafe(now)) {
        return;
    }
    dira.push_back(a);

    if (now[0] == 0 && now[1] == 0 && now[2] == 0 && now[3] == 0) {
        count++;
        cout << "walk way" << count << "way\n";
        display(dira);
        path(dira);
        cout << endl;
        return;
    }

    for (size_t i = 0; i < 4; ++i) {
        if (now[i] == now[0]) { // 物体和农夫在同一侧
            vector<int> temp = now; // 备份当前状态
            now[i] =!now[i]; // 移动物体
            if (i!= 0) {
                now[0] =!now[0]; // 移动农夫
            }
            backtracking(now, dira, step + 1); // 递归调用
            now = temp; // 恢复当前状态
        }
    }
}

int main() {
    vector<int> now = { 1, 1, 1, 1 }; // 农夫、狼、鸡、谷子的初始位置都在河的一侧
    vector<int> dira;
    backtracking(now, dira, 0); 
    return 0;
}